//给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。 
//
// 子数组是数组中元素的连续非空序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,1], k = 2
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3], k = 3
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 2 * 10⁴ 
// -1000 <= nums[i] <= 1000 
// -10⁷ <= k <= 10⁷ 
// 
//
// Related Topics 数组 哈希表 前缀和 👍 2372 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2024-06-05 11:49:27
 * @description 560.和为 K 的子数组
 */
public class SubarraySumEqualsK{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SubarraySumEqualsK fun=new SubarraySumEqualsK();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/*利用hash表优化，计算前缀和
	 * j--i的和为K可以表示为pre[i]-pre[j-1]
	 * 将当前的和存入map中，如果存在【当前值-k】的map
	 * 则结果加上map的值
	 * */
	public int subarraySum(int[] nums, int k) {
		int res=0,pre=0;
		Map<Integer,Integer> map=new HashMap<>();
		map.put(0,1);
		for (int num : nums) {
			pre+=num;
			if(map.containsKey(pre-k)){
				res+=map.get(pre-k);
			}
			map.put(pre,map.getOrDefault(pre,0)+1);
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
